package fast_sorting;

public class FastSorting {

	/*
	 * 快速排序：
	 * 第一轮：
	 * 用第一个值作为关键数据，
	 * 用关键数据从数组后面开始比较，如果遇到小于关键数据的数，就交换位置
	 * 再从数组的前面开始比较，如果遇到大于关键数据的数，就交换位置
	 * 一直循环，直到其左边没有比关键数据大的，右边没有比关键数据小的，则结束循环
	 * 
	 * 依此递归
	 * 
	 * 
	 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array={58,34,65,89,74,1,24};
		sort(array,0,array.length-1);
		//遍历出排序后的数组
		System.out.println("********************遍历出排序后的数组**************************");
		for (int i : array) {
			System.out.print(i+" ");
		}
		
		
	}
	
	//快速排序
	private static int  fastSorting(int[] array,int i,int j) {
	
		int key=array[i];
		while(i<j) {
			
			while(array[j]>key&&i<j) {
				j--;}
				array[i]=array[j];
				
				while(array[i]<=key&&j>i) {
					i++;}
					array[j]=array[i];	

		}
		
		//当i=j就结束循环
		array[j]=key;
		return j;
	}
	
	//排序算法，递归调用
	public static void sort(int[] array,int i,int j) {
		if(i>=j) {
			return ;
		}
		//完成第一轮排序
		int index=fastSorting(array,i,j);
		//对左边部分进行排序
		sort(array,i,index-1);
		//对右边部分进行排序
		sort(array,index+1,j);
		
	}

}
